{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Distribute Coins in Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distributeCoins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在二叉树中分配硬币"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个有 <code>n</code> 个结点的二叉树的根结点 <code>root</code> ，其中树中每个结点 <code>node</code> 都对应有 <code>node.val</code> 枚硬币。整棵树上一共有 <code>n</code> 枚硬币。</p>\n",
    "\n",
    "<p>在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点，或者从子结点移动到父结点。</p>\n",
    "\n",
    "<p>返回使每个结点上 <strong>只有</strong> 一枚硬币所需的 <strong>最少</strong> 移动次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/18/tree1.png\" style=\"width: 250px; height: 236px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,0,0]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>一枚硬币从根结点移动到左子结点，一枚硬币从根结点移动到右子结点。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/18/tree2.png\" style=\"width: 250px; height: 236px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0,3,0]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>将两枚硬币从根结点的左子结点移动到根结点（两次移动）。然后，将一枚硬币从根结点移动到右子结点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目为 <code>n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= n</code></li>\n",
    "\t<li>所有 <code>Node.val</code> 的值之和是 <code>n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [distribute-coins-in-binary-tree](https://leetcode.cn/problems/distribute-coins-in-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [distribute-coins-in-binary-tree](https://leetcode.cn/problems/distribute-coins-in-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,0,0]', '[0,3,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def distributeCoins(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ans =0 \n",
    "        def report_coins(root):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            size_left, coins_left = report_coins(root.left)\n",
    "            size_right, coins_right =report_coins(root.right)\n",
    "            \n",
    "            total_coins =  coins_left+coins_right + root.val\n",
    "            total_size =  size_left+size_right+1\n",
    "            \n",
    "            coin_needed = total_size-total_coins\n",
    "            ans+=abs(coin_needed)\n",
    "            return total_size,total_coins\n",
    "        \n",
    "        report_coins(root)\n",
    "        return ans\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distributeCoins(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.res = 0\n",
    "        def dfs(root):\n",
    "            # left, right = root.left, root.right\n",
    "            # if left:\n",
    "            #     dfs(left)\n",
    "\n",
    "            # if right:\n",
    "            #     dfs(right)\n",
    "            # if left.val !=1:\n",
    "            #     root.val +=\n",
    "            if not root:\n",
    "                return 1\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            self.res += abs(left-1)+abs(right-1)\n",
    "            root.val += left -1 + right -1\n",
    "            return root.val\n",
    "\n",
    "        dfs(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "def num(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    return 1 + num(root.left) + num(root.right)\n",
    "\n",
    "\n",
    "def val(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    return root.val + val(root.left) + val(root.right)\n",
    "\n",
    "\n",
    "def send(root, val):\n",
    "    if root.left is None and root.right is None:\n",
    "        return val\n",
    "    \n",
    "    root.val += val\n",
    "    return Solution().distributeCoins(root) + val\n",
    "\n",
    "\n",
    "def getFrom(root, val):\n",
    "    if root.left is None and root.right is None:\n",
    "        return val\n",
    "    \n",
    "    root.val -= val\n",
    "    return Solution().distributeCoins(root) + val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    # def Solution(self):\n",
    "    #     self.res = 0\n",
    "    \n",
    "    def distributeCoins(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        leftnum = num(root.left)\n",
    "        rightnum = num(root.right)\n",
    "        \n",
    "        leftval = val(root.left)\n",
    "        rightval = val(root.right)\n",
    "        \n",
    "        f = 0\n",
    "        if root.left is not None:\n",
    "            if leftnum < leftval:\n",
    "                f += getFrom(root.left, leftval - leftnum)\n",
    "                # print(f)\n",
    "            elif leftnum > leftval:\n",
    "                f += send(root.left, leftnum - leftval)\n",
    "            else:\n",
    "                f += self.distributeCoins(root.left)\n",
    "        # print(root.val, f)\n",
    "        \n",
    "        if root.right is not None:\n",
    "            if rightnum < rightval:\n",
    "                f += getFrom(root.right, rightval - rightnum)\n",
    "            elif rightnum > rightval:\n",
    "                f += send(root.right, rightnum - rightval)\n",
    "            else:\n",
    "                f += self.distributeCoins(root.right)\n",
    "        print(f)\n",
    "        \n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def distributeCoins(self, root: TreeNode) -> int:\n",
    "        self.result = 0\n",
    "        def helper(root):\n",
    "            if root == None:\n",
    "                return 0\n",
    "            left = helper(root.left)\n",
    "            right = helper(root.right)\n",
    "            self.result += abs(left) + abs(right)\n",
    "            return root.val + left + right - 1\n",
    "        helper(root)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            self.ans += abs(l) + abs(r)\n",
    "            return node.val + l + r -1\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def nodesAndCoins(self,r):\n",
    "        # return nodes nums and coins\n",
    "        if r:\n",
    "            left_n,left_c,left_r = self.nodesAndCoins(r.left)\n",
    "            right_n,right_c,right_r = self.nodesAndCoins(r.right)\n",
    "\n",
    "            nodes_num = 1 + left_n + right_n\n",
    "            coins_num = r.val + left_c + right_c\n",
    "            res = abs(coins_num-nodes_num) + left_r + right_r\n",
    "            return nodes_num,coins_num,res\n",
    "        else:\n",
    "            return 0, 0, 0\n",
    "    def distributeCoins(self, root: TreeNode) -> int:\n",
    "        if root:\n",
    "            _,_,r = self.nodesAndCoins(root)\n",
    "            return r\n",
    "        else:\n",
    "            return 0\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: TreeNode) -> int:\n",
    "        def recurse(node):\n",
    "            if node==None:\n",
    "                return 0\n",
    "            cnt = 0\n",
    "            if node.left:\n",
    "                cnt += recurse(node.left)\n",
    "                node.val += node.left.val-1\n",
    "                cnt += abs( node.left.val-1)\n",
    "            if node.right:\n",
    "                cnt += recurse(node.right)\n",
    "                node.val += node.right.val-1\n",
    "                cnt += abs( node.right.val-1)\n",
    "            return cnt \n",
    "        return recurse(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        \n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            \n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "\n",
    "            nv = l + r + node.val - 1\n",
    "            self.ans += abs(nv)\n",
    "            return nv\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def distributeCoins(self, root: TreeNode) -> int:\n",
    "        self.lrd(root)\n",
    "        return self.res\n",
    "\n",
    "    def lrd(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.left:\n",
    "            root.val += self.lrd(root.left)\n",
    "        if root.right:\n",
    "            root.val += self.lrd(root.right)\n",
    "        \n",
    "        self.res += abs(root.val-1)\n",
    "        return root.val-1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        def over_coin(root):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return 0\n",
    "            l = over_coin(root.left)\n",
    "            r = over_coin(root.right)\n",
    "            ans += abs(l) + abs(r)\n",
    "            \n",
    "            return root.val + l + r - 1\n",
    "        \n",
    "        over_coin(root)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: TreeNode) -> int:\n",
    "        self.result = 0\n",
    "        self.dfs(root)\n",
    "        return self.result\n",
    "\n",
    "    #计算以node结点的树:每个结点分1个金币之后 本结点多余或少的数量\n",
    "    def dfs(self, node:TreeNode)-> int:\n",
    "        if not node:\n",
    "            return 0\n",
    "        right_quality = self.dfs(node.right)\n",
    "        left_quality = self.dfs(node.left)\n",
    "        #业务处理 node节点与它的子节点之间需要移动金币的数量\n",
    "        self.result += abs(right_quality) + abs(left_quality)\n",
    "        return node.val - 1 + left_quality + right_quality"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: TreeNode) -> int:\n",
    "        @lru_cache(None)\n",
    "        def childNum(root:TreeNode) -> int:\n",
    "            if root==None: return 0\n",
    "            return 1 + childNum(root.left) + childNum(root.right)\n",
    "        @lru_cache(None)\n",
    "        def money(root:TreeNode) -> int:\n",
    "            if root==None: return 0\n",
    "            return root.val + money(root.left) + money(root.right)\n",
    "        def getAnswer(root:TreeNode) -> int:\n",
    "            if root==None: return 0\n",
    "            if root.left==None and root.right==None: return 0 \n",
    "            x = money(root.left) - childNum(root.left)\n",
    "            y = money(root.right) - childNum(root.right)\n",
    "            rv = getAnswer(root.left) + getAnswer(root.right)\n",
    "            # move all money to root \n",
    "            rv += min(abs(x),abs(y)) \n",
    "            # split all money \n",
    "            rv += max(abs(x),abs(y))\n",
    "            return rv\n",
    "        return getAnswer(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: TreeNode) -> int:\n",
    "        self.queue = []\n",
    "        _ = self.dfs(root, None)\n",
    "        self.ans = 0\n",
    "        while self.queue:\n",
    "            self.adjust(self.queue.pop())\n",
    "        return self.ans \n",
    "    \n",
    "    def adjust(self, node):\n",
    "        if node.val <= 1:\n",
    "            return \n",
    "        \n",
    "        if node.left_diff < 0:\n",
    "            supply = min(0 - node.left_diff, node.val - 1)\n",
    "            node.left.val += supply\n",
    "            node.val -= supply\n",
    "            node.left_diff += supply\n",
    "            self.queue.append(node.left)\n",
    "            self.ans += supply\n",
    "        \n",
    "        if node.val <= 1:\n",
    "            return \n",
    "        \n",
    "        if node.right_diff < 0:\n",
    "            supply = min(0 - node.right_diff, node.val - 1)\n",
    "            node.right.val += supply\n",
    "            node.val -= supply\n",
    "            node.right_diff += supply\n",
    "            self.queue.append(node.right)\n",
    "            self.ans += supply\n",
    "        \n",
    "        if node.val <= 1:\n",
    "            return \n",
    "        \n",
    "        supply = node.val - 1\n",
    "        node.parent.val += supply\n",
    "        node.val -= supply\n",
    "        if node.parent.left is node:\n",
    "            node.parent.left_diff -= supply\n",
    "        else:\n",
    "            node.parent.right_diff -= supply\n",
    "        self.queue.append(node.parent)\n",
    "        self.ans += supply\n",
    "\n",
    "\n",
    "    def dfs(self, node, parent):\n",
    "        if node is None:\n",
    "            return 0\n",
    "        \n",
    "        node.parent = parent\n",
    "        \n",
    "        if node.val > 1:\n",
    "            self.queue.append(node)\n",
    "        \n",
    "        node.left_diff, node.right_diff = self.dfs(node.left, node), self.dfs(node.right, node)\n",
    "        return node.left_diff + node.right_diff + node.val - 1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: TreeNode) -> int:\n",
    "        def get_help(root):\n",
    "            node_num = 0\n",
    "            coin_num = 0\n",
    "            if not root: return 0, 0, 0\n",
    "            node_num = 1\n",
    "            coin_num = root.val\n",
    "            ans = 0\n",
    "            tmp1, node_num1, coin_num1 = get_help(root.left)\n",
    "            ans = ans + tmp1 + abs(node_num1 - coin_num1)\n",
    "            tmp2, node_num2, coin_num2 = get_help(root.right)\n",
    "            ans = ans + tmp2 + abs(node_num2 - coin_num2)\n",
    "            node_num = node_num + node_num1 + node_num2\n",
    "            coin_num = coin_num + coin_num1 + coin_num2\n",
    "            return ans, node_num, coin_num\n",
    "        ans = get_help(root)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def distributeCoins(self, root):\n",
    "        self.ans = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node: return 0\n",
    "            L, R = dfs(node.left), dfs(node.right)\n",
    "            self.ans += abs(L) + abs(R)\n",
    "            return node.val + L + R - 1\n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(nd):\n",
    "            nonlocal res\n",
    "            if not nd: return 0\n",
    "            l, r = dfs(nd.left), dfs(nd.right)\n",
    "            res += abs(l) + abs(r)\n",
    "            return nd.val + l + r - 1\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
    "        move_count = 0\n",
    "        def dfs(node):\n",
    "            nonlocal move_count\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            # +: means need move in; -: can move out\n",
    "            if not node.left and not node.right:\n",
    "                return 1 - node.val\n",
    "\n",
    "            left_count = dfs(node.left)\n",
    "            right_count = dfs(node.right)\n",
    "\n",
    "            print(node.val, left_count, right_count)\n",
    "            mul = left_count * right_count\n",
    "            if mul >= 0:\n",
    "                move_count += abs(left_count + right_count)\n",
    "            else:\n",
    "                move_count += abs(right_count - left_count)\n",
    "            return 1 - (node.val - left_count - right_count)\n",
    "\n",
    "        dfs(root)\n",
    "        return move_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
    "        info, n = {}, 0\n",
    "        def dfs(node):\n",
    "            #返回形式形如[a, b, c, d]分别表示左边的nodes数，左边的coins数，右边的……\n",
    "            nonlocal n\n",
    "            if not node:\n",
    "                return [0, 0, 0, 0]\n",
    "            n += 1\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            res = [l[0] + l[2] + 1 if node.left else 0, l[1] + l[3] + node.left.val if node.left else 0, r[0] + r[2] + 1 if node.right else 0, r[1] + r[3] + node.right.val if node.right else 0]\n",
    "            info[node] = res\n",
    "            return res\n",
    "        dfs(root)\n",
    "        ans = 0\n",
    "        def dfs2(node):\n",
    "            nonlocal ans\n",
    "            if not node: return \n",
    "            left_nodes, left_coins, right_nodes, right_coins = info[node]\n",
    "            fa_nodes = n - 1 - left_nodes - right_nodes\n",
    "            fa_coins = n - node.val - right_coins - left_coins\n",
    "            ans += abs(fa_coins - fa_nodes) + abs(left_coins - left_nodes) + abs(right_coins - right_nodes)\n",
    "            dfs2(node.left)\n",
    "            dfs2(node.right)\n",
    "        dfs2(root)\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: [TreeNode]) -> int:\n",
    "        dc=defaultdict(list)\n",
    "        # [以root树的节点总数， 以root的树硬币总数, 从父亲下移到root硬币个数，需要从左子树移到root个数，需要从右子树移过root个数]\n",
    "\n",
    "        def dfs(root:TreeNode):     #这一步，计算以当前root为根节点的树（包含其子树）的节点数数目和硬币个数\n",
    "            an=[0,0,0,0,0]\n",
    "            if not root: return an\n",
    "            tmpl=dfs(root.left)\n",
    "            tmpr=dfs(root.right)\n",
    "            an[0]=tmpl[0]+1+tmpr[0]\n",
    "            an[1]=tmpl[1]+root.val+tmpr[1]\n",
    "            dc[root]=an\n",
    "            return an\n",
    "\n",
    "        def dfsmovecoin(root:TreeNode):     #这一步，计算以当前root为根节点的树（包含其子树）的节点数数目和硬币个数\n",
    "            if not root: return 0           #每次返回调整好root和以下的子树的硬币需要的步骤\n",
    "\n",
    "            tmpl=0\n",
    "            tmpr=0\n",
    "            if root.left:\n",
    "                tmpl=dfsmovecoin(root.left)         #左子树内部调整需要的个数\n",
    "                tmpl+=abs(dc[root.left][0]-dc[root.left][1])\n",
    "\n",
    "            if root.right:\n",
    "                tmpr=dfsmovecoin(root.right)        #右子树内部调整需要的个数\n",
    "                tmpr+=abs(dc[root.right][0]-dc[root.right][1])\n",
    "\n",
    "            tmproot=abs(dc[root][0]-dc[root][1])\n",
    "#            print(\"val:\",root.val, tmproot,tmpl,tmpr)\n",
    "            return tmpl+tmpr+tmproot\n",
    "\n",
    "        dc[root]=dfs(root)\n",
    "#        print(dc)\n",
    "        return dfsmovecoin(root)//2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=0\n",
    "        def g(r):\n",
    "          nonlocal ans\n",
    "          if r is None:\n",
    "              return 0  \n",
    "          c=(r.val+g(r.left)+g(r.right)-1)\n",
    "          ans+=abs(c)\n",
    "          return c\n",
    "        g(root)  \n",
    "        return ans   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            # if not root:\n",
    "            #     return 0, 0\n",
    "            # leftCoin, leftNode = dfs(root.left)\n",
    "            # rightCoin, rightNode = dfs(root.right)\n",
    "            # coins = leftCoin + rightCoin + root.val\n",
    "            # nodes = leftNode + rightNode + 1\n",
    "            # self.res += abs(coins - nodes)\n",
    "            # return coins, nodes\n",
    "            if not root:\n",
    "                return 0\n",
    "            d = dfs(root.left) + dfs(root.right) + root.val - 1\n",
    "            self.res += abs(d)\n",
    "            return d\n",
    "\n",
    "        self.res = 0\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
    "#         def dfs(root):\n",
    "#             # if not root:\n",
    "#             #     return 0, 0\n",
    "#             # leftCoin, leftNode = dfs(root.left)\n",
    "#             # rightCoin, rightNode = dfs(root.right)\n",
    "#             # coins = leftCoin + rightCoin + root.val\n",
    "#             # nodes = leftNode + rightNode + 1\n",
    "#             # self.res += abs(coins - nodes)\n",
    "#             # return coins, nodes\n",
    "#             if not root:\n",
    "#                 return 0\n",
    "#             d = dfs(root.left) + dfs(root.right) + root.val - 1\n",
    "#             self.res += abs(d)\n",
    "#             return d\n",
    "\n",
    "#         self.res = 0\n",
    "#         dfs(root)\n",
    "#         return self.res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
    "#         def dfs(root):\n",
    "#             if not root:\n",
    "#                 return 0\n",
    "#             # coins = leftCoin + rightCoin + root.val\n",
    "#             # nodes = leftNode + rightNode + 1\n",
    "#             # coins - nodes = (leftCoin - leftNode) + (rightCoin - rightNode) + root.val + 1\n",
    "#             d = dfs(root.left) + dfs(root.right) + root.val - 1\n",
    "#             self.res += abs(d)\n",
    "#             return d\n",
    "#         self.res = 0\n",
    "#         dfs(root)\n",
    "#         return self.res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
    "#         def dfs(root):\n",
    "#             if not root:\n",
    "#                 return 0, 0\n",
    "#             leftCoin, leftNode = dfs(root.left)\n",
    "#             rightCoin, rightNode = dfs(root.right)\n",
    "#             coins = leftCoin + rightCoin + root.val\n",
    "#             nodes = leftNode + rightNode + 1\n",
    "#             self.res += abs(coins - nodes)\n",
    "#             return coins, nodes\n",
    "#         self.res = 0\n",
    "#         dfs(root)\n",
    "#         return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def helper(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        leftRes = self.helper(root.left)\n",
    "        rightRes = self.helper(root.right)\n",
    "\n",
    "        self.res += abs(leftRes) + abs(rightRes)\n",
    "\n",
    "        return leftRes + rightRes + root.val - 1\n",
    "    def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        self.helper(root)\n",
    "        return self.res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
